Minimum domino rotations for equal row

Time: O(N); Space: O(1); medium

In a row of dominoes, A[i] and B[i] represent the top and bottom halves of the i-th domino. (A domino is a tile with two numbers from 1 to 6 - one on each half of the tile.) We may rotate the i-th domino, so that A[i] and B[i] swap values.

Return the minimum number of rotations so that all the values in A are the same, or all the values in B are the same. If it cannot be done, return -1.

Example 1:

Input: A = [2,1,2,4,2,2], B = [5,2,6,2,3,2]

Output: 2

Explanation:

  • The first figure represents the dominoes as given by A and B: before we do any rotations.

  • If we rotate the second and fourth dominoes, we can make every value in the top row equal to 2, as indicated by the second figure.

Example 2:

Input: A = [3,5,1,2,3], B = [3,6,3,3,4]

Output: -1

Explanation:

  • In this case, it is not possible to rotate the dominoes to make one row of values equal.

Notes:

  • 1 <= A[i], B[i] <= 6

  • 2 <= len(A) == len(B) <= 20000

[9]:

from functools import reduce

class Solution1(object):
    def minDominoRotations(self, A, B):
        """
        :type A: List[int]
        :type B: List[int]
        :rtype: int
        """
        intersect = reduce(set.__and__, [set(d) for d in zip(A, B)])
        if not intersect:
            return -1
        x = intersect.pop()
        return min(len(A) - A.count(x), len(B) - B.count(x))

[10]:

s = Solution1()
A = [2,1,2,4,2,2]
B = [5,2,6,2,3,2]
assert s.minDominoRotations(A, B) == 2
A = [3,5,1,2,3]
B = [3,6,3,3,4]
assert s.minDominoRotations(A, B) == -1